package org.example.day04;

import java.util.*;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO+
 * 项目组共有N个开发人员，项目经理接到了M个独立的需求，每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作。
 * 假定各个需求直接无任何先后依赖关系，请设计算法帮助项目经理进行工作安排，使整个项目能用最少的时间交付。
 * @date 2024/3/11 15:22
 */
//需要优化
public class test068 {
    static int distributeTasks(List<Integer> workloads, int N) {
        // 降序排序任务工作量
        Collections.sort(workloads, Collections.reverseOrder());
        int[] employee_hours = new int[N]; // 员工的工作时间数组
        int[] min_time = {Integer.MAX_VALUE}; // 最少完成时间

        // 使用回溯法尝试所有分配方案
        class Util {
            void backtrack(int i) {
                if (i == workloads.size()) { // 所有任务都已经分配完
                    min_time[0] = Math.min(min_time[0], Arrays.stream(employee_hours).max().getAsInt()); // 更新最少完成时间
                    return;
                }
                for (int j = 0; j < N; j++) { // 遍历所有员工
                    if (employee_hours[j] + workloads.get(i) > min_time[0]) continue; // 跳过超时方案
                    employee_hours[j] += workloads.get(i); // 分配任务给员工
                    backtrack(i + 1); // 继续分配下一个任务
                    employee_hours[j] -= workloads.get(i); // 回溯，取消分配任务
                }
            }
        }

        new Util().backtrack(0); // 从第一个任务开始回溯
        return min_time[0]; // 返回最少完成时间
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> workloads = new ArrayList<>();
        // 读取工作量
        String[] inputs = scanner.nextLine().split(" ");
        for (String input : inputs) {
            workloads.add(Integer.parseInt(input));
        }
        // 读取员工数量
        int N = scanner.nextInt();
        System.out.println(distributeTasks(workloads, N));
    }
}


